là tập các đỉnh mà khi loại bỏ chúng sẽ làm cho đồ thị mất tính liên thông.
Lát cắt cạnh
là tập tất cả các cạnh có một đầu thuộc tập đỉnh con S và đầu kia thuộc V(G)\S.
Liên thông
Nếu giữa hai điểm bất kỳ của một đồ thị đều có thể thiết lập một đường đi từ đỉnh này đến đỉnh kia, đồ thị được coi là liên thông; nếu không, đồ thị được coi là không liên thông. Một đồ thị được coi là hoàn toàn không liên thông nếu không có đường đi giữa hai đỉnh bất kỳ trong đồ thị. Đây chỉ là một cái tên khác để miêu tả một đồ thị rỗng hoặc một tập độc lập.Một đồ thị có hướng được coi là liên thông mạnh nếu từ mọi đỉnh đều đến được mọi đỉnh khác. Ngược lại, đồ thị có hướng được coi là liên thông yếu nếu đồ thị vô hướng nền tảng của nó là đồ thị liên thông.
Lưới (còn gọi là mạng, mạng lưới)
Trong một số tài liệu về lý thuyết đồ thị, thuật ngữ lưới (network) được coi là từ đồng nghĩa với đồ thị có trọng số. Một lưới có thể có hướng hoặc vô hướng. Lưới có thể chứa các đỉnh (nút) đặc biệt, chẳng hạn đỉnh phát hoặc đỉnh thu.
